/**
 * 
 */
package com.gwcloud.leetcode.hot100;

/**
 * @ClassName   : Leetcode0221 
 * @author      : ganwei 
 * @date        : 2020年5月21日
 * @Description : Leetcode0221 最大正方形
 */
public class Leetcode0221 {
    /**
     * -解题思路,动态规划思路
     */
	public int maximalSquare(char[][] matrix) {
    	int maxside = 0;
    	if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
    		return 0;
    	}
    	
    	int rows = matrix.length, columns = matrix[0].length;
        int[][] dp = new int[rows][columns];
        
        for(int i = 0; i < rows; i++){
        	for(int j = 0; j < columns; j++){
        		if(matrix[i][j] == '1'){
        			if(i == 0 || j == 0){
        				dp[i][j] = 1;
        			}else{
        				dp[i][j] = Math.min(dp[i-1][j], Math.min(dp[i-1][j-1], dp[i][j-1])) + 1;
        			}
        			maxside = Math.max(maxside, dp[i][j]);
        		}
        	}
        }
		
    	return maxside*maxside;
    }
    
	/**
	 * -主函数
	 */
    public static void main(String[] args){
    	
    }
}
